//----------------------------------------------------------------------最小树形图
#define M 101
#define type int
#define inf INT_MAX
#define FF(i,n) for(int i=0;i<(n);i++)
#define CC(a,x) memset(a,x,sizeof(a))
struct Node{
	int u , v;
	type cost;
}E[M*M];
int pre[M],ID[M],vis[M];
type In[M];

type Directed_MST(int root,int NV,int NE) {
	type ret = 0;
	while(true) {
		//1.找最小入边
		FF(i,NV) In[i] = inf;
		FF(i,NE) {
			int u = E[i].u;
			int v = E[i].v;
			if(E[i].cost < In[v] && u != v) {
				pre[v] = u;
				In[v] = E[i].cost;
			}
		}
		FF(i,NV) {
			if(i == root) continue;
			if(In[i] == inf)	return -1;//除了跟以外有点没有入边,则根无法到达它
		}
		//2.找环
		int cntnode = 0;
		CC(ID,-1);
		CC(vis,-1);
		In[root] = 0;
		FF(i,NV) {//标记每个环
			ret += In[i];
			int v = i;
			while(vis[v] != i && ID[v] == -1 && v != root) {
				vis[v] = i;
				v = pre[v];
			}
			if(v != root && ID[v] == -1) {
				for(int u = pre[v] ; u != v ; u = pre[u]) {
					ID[u] = cntnode;
				}
				ID[v] = cntnode ++;
			}
		}
		if(cntnode == 0)	break;//无环
		FF(i,NV) if(ID[i] == -1) {
			ID[i] = cntnode ++;
		}
		//3.缩点,重新标记
		FF(i,NE) {
			int v = E[i].v;
			E[i].u = ID[E[i].u];
			E[i].v = ID[E[i].v];
			if(E[i].u != E[i].v) {
				E[i].cost -= In[v];
			}
		}
		NV = cntnode;
		root = ID[root];
	}
	return ret;
}
